package com.apkcore.bl;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/throne-inheritance/
 * 题意就像是明朝一样，嫡长子，就算长子死了，也传给孙子，然后孙子无后，传叔叔的那种
 * 1. 可以构建多叉树，父节点下面有多个子节点，子节点又有多个子节点，采用前序遍历就行了
 * 2. 也可以使用一个单向链表就行了，把父的儿子都插到父的大儿子们的后面，维护一条链表
 */
public class _1600皇位继承顺序 {

    static class Node {
        String name;
        Node next;
        Node lastChild;
        boolean isDeleted = false;

        public Node(String name) {
            this.name = name;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "name='" + name + '\'' +
                    ", next=" + next +
                    ", lastChild=" + lastChild +
                    ", isDeleted=" + isDeleted +
                    '}';
        }
    }

    public static void main(String[] args) {
        ThroneInheritance throneInheritance = new ThroneInheritance("king");
        throneInheritance.birth("king", "andy");
        throneInheritance.birth("andy", "andy2222");
        throneInheritance.birth("king", "bob");
        throneInheritance.birth("king", "catherine");
        throneInheritance.birth("andy2222", "dsdf");
        throneInheritance.birth("andy", "aaa");
//        throneInheritance.death("king");

        System.out.println(throneInheritance.getInheritanceOrder());
    }

    static class ThroneInheritance {


        Map<String, Node> map = new HashMap<>();
        Node head = new Node("");
        Node tail = new Node("");

        public ThroneInheritance(String kingName) {
            Node root = new Node(kingName);
            root.next = tail;
            head.next = root;
            map.put(kingName, root);
        }

        /**
         * 表示 parentName 新拥有了一个名为 childName 的孩子。
         */
        public void birth(String parentName, String childName) {
            Node node = new Node(childName);
            map.put(childName, node);

            Node p = map.get(parentName);
            Node temp = p;
            while (temp.lastChild != null) {
                temp = temp.lastChild;
            }
            node.next = temp.next;
            temp.next = node;
            p.lastChild = node;
        }

        /**
         * 表示名为 name 的人死亡。一个人的死亡不会影响 Successor 函数，
         * 也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。
         */
        public void death(String name) {
            Node node = map.get(name);
            node.isDeleted = true;

        }

        /**
         * 返回 除去 死亡人员的当前继承顺序列表。
         */
        public List<String> getInheritanceOrder() {
            List<String> ans = new ArrayList<>();
            Node temp = head.next;
            while (temp.next != null) {
                if (!temp.isDeleted) {
                    ans.add(temp.name);
                }
                temp = temp.next;
            }

            return ans;
        }

    }
}
